class Solution {
    //DFS
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //两个都为空
        if(p==null&&q==null){
            return true;
        }
        //一个为空，一个不为空
        if(p==null||q==null){
            return false;
        }
        if(p.val!=q.val){
            return false;
        }
        //p和q相同，再判断左数和右数是否都相同
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }

    /*
     * BFS
     *
     * */
    public boolean isSameTree2(TreeNode p, TreeNode q) {
        Queue<TreeNode> queueP = new LinkedList<>();
        Queue<TreeNode> queueQ = new LinkedList<>();
        queueP.offer(p);
        queueQ.offer(q);
        while(!queueP.isEmpty() && !queueQ.isEmpty()){
            TreeNode np = queueP.poll();
            TreeNode nq = queueQ.poll();
            if(np == null && nq == null){
                continue;
            }
            if(np == null || nq == null){
                return false;
            }
            if(np.val != nq.val){
                return false;
            }
            //能走到这一步，np，nq绝对不为空
            queueP.offer(np.left);
            queueP.offer(np.right);
            queueQ.offer(nq.left);
            queueQ.offer(nq.right);
        }
        return true;
    }
}